package leetcode;

import java.util.*;

/**
 * @author ht
 * @create 2025-06-13 21:38
 * @desc
 **/
public class T349 {

    public boolean isAnagram(String s, String t) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(String.valueOf(s.charAt(i)), map.getOrDefault(String.valueOf(s.charAt(i)), 0) + 1);
        }

        for (int i = 0; i < t.length(); i++) {
            String s1 = String.valueOf(t.charAt(i));
            Integer integer = map.get(s1);
            if(integer != null && integer > 0) {
                map.put(s1, integer - 1);
            } else {
                return false;
            }
        }

        return map.isEmpty();
    }

    public boolean wordPattern(String pattern, String s) {
        String[] split = s.split(" ");
        if(pattern.length() != split.length) {
            return false;
        }

        Set<String> sSet = new HashSet<>();
        for (String str : split) {
            sSet.add(str);
        }

        Set<Character> pSet = new HashSet<>();
        for (int i = 0; i < pattern.length(); i++) {
            pSet.add(pattern.charAt(i));
        }

        Set<String> cSet = new HashSet<>();
        for (int i = 0; i < pattern.length(); i++) {
            String p = String.valueOf(pattern.charAt(i));
            String str = split[i];
            cSet.add(p + str);
        }
        return sSet.size() == pSet.size() && cSet.size() == sSet.size();

    }

    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>();
        Map<Character, Character> t2s = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char x = s.charAt(i);
            char y = t.charAt(i);

            if(s2t.containsKey(x) && s2t.get(x) != y || t2s.containsKey(y) && t2s.get(y) != x) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        ArrayList<Character> arrayList = new ArrayList<>(map.keySet());
        arrayList.sort((o1, o2) -> map.get(o2) - map.get(o1));
        StringBuilder sb = new StringBuilder();
        for (Character character : arrayList) {
            int count = map.get(character);
            for (int i = 0; i < count; i++) {
                sb.append(character);
            }
        }
        return sb.toString();
    }

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if(i != j) {
                    int numI = nums[i];
                    int numJ = nums[j];
                    if(numI + numJ == target) {
                        return new int[]{i, j};
                    }
                }
            }
        }
        return new int[]{};
    }

     public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}ListNode(int val) { this.val = val; }

         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next  = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    public boolean isValid(String s) {
        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("[", "]");
        map.put("{", "}");
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            String s1 = String.valueOf(s.charAt(i));
            if(map.containsKey(s1)) {
                stack.push(s1);
            } else {
                if(stack.isEmpty()) {
                    return false;
                }
                String pop = stack.pop();
                if(!map.get(pop).equals(s1)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }

        if(p == null || q == null) {
            return false;
        }

        Queue<TreeNode> queueP = new LinkedList<TreeNode>();
        Queue<TreeNode> queueQ = new LinkedList<TreeNode>();
        queueP.offer(p);
        queueQ.offer(q);

        while(!queueP.isEmpty() && !queueQ.isEmpty()){
            TreeNode pollP = queueP.poll();
            TreeNode pollQ = queueQ.poll();
            if(pollP.val != pollQ.val) {
                return false;
            }
            if(pollP.left != null && pollQ.left != null) {
                queueP.offer(pollP.left);
                queueQ.offer(pollQ.left);
            } else if(pollP.left != null || pollQ.left != null) {
                return false;
            }
            if(pollP.right != null && pollQ.right != null) {
                queueP.offer(pollP.right);
                queueQ.offer(pollQ.right);
            } else if(pollP.right != null || pollQ.right != null) {
                return false;
            }
        }

        return queueP.isEmpty() && queueQ.isEmpty();
    }


    public static void main(String[] args) {
        //int i = 12;
        ////System.out.println(i%10);
        ////System.out.println(12/10);
        //
        //int j = 16456;
        //while (j > 0) {
        //    System.out.println(j%10);
        //    j = j/10;
        //}
        //String s = "12345";
        //
        //for (int i = 0; i < s.length(); i++) {
        //    char charAt = s.charAt(i);
        //    System.out.println(Integer.valueOf(String.valueOf(charAt)));
        //}
        //
        //System.out.println(Integer.valueOf(s));
        //ListNode listNode = new ListNode(1);
        //ListNode listNodeNew = listNode;
        //listNode.val = 2;
        //System.out.println(listNode);
        //System.out.println(listNodeNew);
        //String s = "ACB";
        //char charAt = s.charAt(0);
        //int i = charAt + '1';
        System.out.println(2 % 1);
    }

    public String reverseStr(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length() ; i+=2*k) {
            if((i + 2*k) <= s.length()) {
                System.out.println("up" + i);
                sb.append(new StringBuilder(s.substring(i, i + k)).reverse());
                sb.append(s.substring(i + k, i + 2*k));
            }

            if((s.length() - i >= k) && (s.length() - i < 2*k)) {
                System.out.println("down" + i);
                sb.append(s.substring(i, s.length()));
            } else {
                sb.append(new StringBuilder(s.substring(i, s.length())).reverse());
            }
        }
        return sb.toString();
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }

        Set<Integer> set2 = new HashSet<>();
        for (int i = 0; i < nums2.length; i++) {
            if(set.contains(nums2[i])) {
                set2.add(nums2[i]);
            }
        }

        int[] arr = new int[set2.size()];
        int i = 0;
        for (Integer integer : set2) {
            arr[i] = integer;
            i++;
        }
        return arr;
    }


}
